#include <iostream>
#include <cmath>
#include <algorithm>

using i64 = long long;

constexpr int N = 2E5 + 5;
constexpr int M = 18;

int n;
int w[N];

int f[N][M];

void init() {
    for (int i = 0; i < M; ++i) {
        for (int j = 0; j + (1 << i) - 1 < n; ++j) {
            f[j][i] = i ? std::max(f[j][i - 1], f[j + (1 << i - 1)][i - 1]) : w[j];
        }
    }
}

int query(int l, int r) {
    int len = r - l + 1;
    int j = std::__lg(len);
    
    return std::max(f[l][j], f[r - (1 << j) + 1][j]);
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    std::cin >> n;
    
    for (int i = 0; i < n; ++i) {
        std::cin >> w[i];
    }
    init();
    
    int m;
    std::cin >> m;

    while (m--) {
        int a, b;
        std::cin >> a >> b;
        --a, --b;
        std::cout << query(a, b) << "\n";
    }
    
    return 0;
}